#include <iostream>
using namespace std;
int inversePairsCore( int *array , int *copy , int begin , int end )
{
    if( begin == end ) {
        copy[begin] = array[begin];
        return 0;
    }
    int mid = (end-begin)/2;
    int left = inversePairsCore( array,copy,begin,mid );
    int right = inversePairsCore( array,copy,begin,mid+1);
    int inverseNumbers = left + right ;
    int i = mid , j = end , k = end;
    while( i >= begin && j >= mid + 1 )
        {
            if( array[i] > array[j] )
            {
                inverseNumbers += j - mid;
                copy[k--] = array[i--];
            }
            else
                copy[k--] = array[j--];
        }
        while( i >= begin )
            copy[k--] = array[i--];
        while( j >= mid + 1 )
            copy[k--] = array[j--];
        i = begin , j = end;
        while( i <= j )
        {
            array[i] = copy[i];
            i++;
        }
        return inverseNumbers;
    }
    return 0;
}

//数组中的逆序对数
int inversePairs( int *array , int length )
{
    int *copy = new int[length];
    int counts = inversePairsCore( array , 0 , ( length - 1 )/2 , length - 1 , copy );
    delete [] copy;
    return counts;
}

int main()
{
    int array[] = { 7 , 5 , 6 , 4 };
    cout<< "inversePairsCounts:\t" << inversePairs( array, 4 ) << endl;
    return 0;
}
